package BackTrackingPackage3;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class combinationSum2_ {
  List<Integer> path = new ArrayList<>();
  List<List<Integer>> result = new ArrayList<>();

  @Test
  public void combinationSum2Test(){
    int[] candidates = new int[]{10,1,2,7,6,1,5};

    List<List<Integer>> lists = combinationSum2(candidates, 8);
    for (List<Integer> list : lists) {
      System.out.println(list.toString());
    }
  }

  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    boolean[] used = new boolean[candidates.length];
    Arrays.fill(used,false);
    backTracking(candidates,target,0,used);
    return result;
  }
  public void backTracking(int[] candidates, int target,int startIndex,boolean[] used){
    if(getSum(path) == target){
      result.add(new ArrayList<>(path));
      return;
    }
    if (getSum(path) > target){
      return;
    }
    for (int i = startIndex ; i < candidates.length ; i++){
      // 如果[1,1,2,3,4,5]
      // 取到第一个1
      // 取到第二个1
      // 取到2
      // 那之后的第一次取就不能是第二个1了, 因为第一次取的第二个1之后的所有结果都在第一个1是第一个1中
      if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;
      path.add(candidates[i]);
      used[i] = true;
      backTracking(candidates,target,i + 1,used);
      path.remove(path.size() - 1);
      used[i] = false;
    }
  }
  public int getSum(List<Integer> list){
    int sum = 0;
    for (Integer integer : list) {
      sum += integer;
    }
    return sum;
  }
}
